package DataStructrue;

//树状数组,支持log(n)的单点与区间的查询与修改
public class TreeArray {
    //设dif为arr的差分数组,则arr的前n项和为sum(sum(dif[j])[i]),即n*sum(dif[i])-sum(dif[i]*(i-1))
    //那么只需要维护 dif[i] 和 dif[i]*(i-1) 两个数组的树状数组即可
    private long[] tree1;//dif[i]树状数组,存储[i-lowBit(i)+1,i]的区间和
    private long[] tree2;//dif[i]*(i-1)树状数组,存储[i-lowBit(i)+1,i]的区间和
    private int N;//元素数量

    public TreeArray(long[] arr){
        this.N=arr.length;
        this.tree1=new long[N+1];//0位置不用
        this.tree2=new long[N+1];//0位置不用
        //初始化
        for (int i = 0; i < N; i++){
            if(i==0) {
                add(tree1,1,arr[0]);
                add(tree2,1,0);
            } else {
                add(tree1,i+1,arr[i]-arr[i-1]);
                add(tree2,i+1,(arr[i]-arr[i-1])*i);
            }
        }
    }
    //保留二进制最后一位1
    private int lowBit(int x) {
        return x & -x;
    }
    //前n项和
    private long pre(long[] arr,int n) {
        long ans = 0;
        for (int i = n; i > 0; i -= lowBit(i)){
            ans += arr[i];
        }
        return ans;
    }
    //将idx位置处+val
    private void add(long[] arr,int idx,long val) {
        //对应的父区间也要+val
        for (int i = idx; i <= N; i += lowBit(i)){
            arr[i] += val;
        }
    }
    //区间修改(增加)
    public void update(int l,int r,long val){
        //只需修改差分数组的两个点即可完成原数组的区间修改
        add(tree1,l+1,val);
        add(tree1,r+2,-val);
        add(tree2,l+1,val*l);
        add(tree2,r+2,-val*(r+1));
    }
    //区间查询
    public long query(int l, int r) {
        return pre(tree1,r+1)*(r+1)-pre(tree2,r+1)-(pre(tree1,l)*l-pre(tree2,l));
    }



}
